package com.lw.leetcode.arr.c;

import com.lw.test.util.Utils;

/**
 * Created with IntelliJ IDEA.
 * c
 * arr
 * 1819. 序列中不同最大公约数的数目
 *
 * @author liw
 * @version 1.0
 * @date 2023/2/9 11:40
 */
public class CountDifferentSubsequenceGCDs {

    public static void main(String[] args) {
        CountDifferentSubsequenceGCDs test = new CountDifferentSubsequenceGCDs();

        // 5
//        int[] arr = {6, 10, 3};

        //
        int[] arr = Utils.getArr(1000, 1, 200000);

        int i = test.countDifferentSubsequenceGCDs(arr);
        System.out.println(i);
    }

    public int countDifferentSubsequenceGCDs(int[] nums) {
        int max = 0;
        int min = nums[0];
        for (int num : nums) {
            max = Math.max(max, num);
            min = gcd(min, num);
        }
        boolean[] flags = new boolean[max + 1];
        for (int num : nums) {
            flags[num] = true;
        }
        int count = 1;
        for (int i = min + 1; i <= max; i++) {
            if (flags[i]) {
                count++;
                continue;
            }
            int item = 0;
            for (int j = i + i; j <= max; j += i) {
                if (!flags[j]) {
                    continue;
                }
                item = item == 0 ? j : gcd(item, j);
                if (item == i) {
                    count++;
                    break;
                }
            }
        }
        return count;
    }

    private int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

}
